#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
#include<vector>
using namespace std;

class Solution {
public:
    int findSubstringInWraproundString(string s) {
        int n = s.size();
        vector<int> dp(n, 1);
        int hash[26] = { 0 };
        int ans = 0;
        for (int i = 1; i < n; ++i)
        {
            if (s[i - 1] + 1 == s[i] || (s[i - 1] == 'z' && s[i] == 'a'))
                dp[i] += dp[i - 1];
        }
        for (int i = 0; i < n; ++i)
            hash[s[i] - 'a'] = max(hash[s[i] - 'a'], dp[i]);
        for (auto x : hash)
            ans += x;
        return ans;
    }

    int visited[7][7] = { 0 };
    bool dfs(vector<vector<char>>& board, int i, int j, string word, int pos)
    {
        if (board[i][j] != word[pos]) return false;
        if (pos == word.size() - 1)return true;
        int dir[4][2] = { {1,0},{-1,0},{0,1},{0,-1} };
        bool res = false;
        for (int k = 0; k < 4; ++k)
        {
            int ti = i + dir[k][0], tj = j + dir[k][1];
            if (ti >= 0 && ti < board.size() && tj >= 0 && tj < board[0].size())
            {
                if (!visited[ti][tj])
                {
                    visited[ti][tj] = true;
                    if (dfs(board, ti, tj, word, pos + 1)) return true;
                    visited[ti][tj] = false;
                }
            }
        }
        return res;
    }

    bool exist(vector<vector<char>>& board, string word) {
        for (int i = 0; i < board.size(); ++i)
        {
            for (int j = 0; j < board[0].size(); ++j)
            {
                visited[i][j] = true;
                if (dfs(board, i, j, word, 0)) return true;
                visited[i][j] = false;
            }
        }
        return false;
    }

    bool vis[16][16] = { 0 };
    int ans = 0;
    void dfs(vector<vector<int>>& grid, int i, int j, int sum)
    {
        ans = max(ans, sum);
        int dics[4][2] = { {1,0},{-1,0},{0,1},{0,-1} };
        for (auto dic : dics)
        {
            int x = i + dic[0], y = j + dic[1];
            if (x >= 0 && x < grid.size() && y >= 0 && y < grid[0].size() && !visited[x][y] && grid[x][y])
            {
                vis[x][y] = true;
                dfs(grid, x, y, sum + grid[x][y]);
                vis[x][y] = false;
            }
        }
    }

    int getMaximumGold(vector<vector<int>>& grid) {
        for (int i = 0; i < grid.size(); ++i)
        {
            for (int j = 0; j < grid[0].size(); ++j)
            {
                if (grid[i][j])
                {
                    vis[i][j] = true;
                    dfs(grid, i, j, grid[i][j]);
                    vis[i][j] = false;
                }
            }
        }
        return ans;
    }
};